"""
https://leetcode.cn/problems/array-partition/description/


561. 数组拆分
简单
相关标签
相关企业
提示
给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。

返回该 最大总和 。

 

示例 1：

输入：nums = [1,4,3,2]
输出：4
解释：所有可能的分法（忽略元素顺序）为：
1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
所以最大总和为 4
示例 2：

输入：nums = [6,2,6,5,1,2]
输出：9
解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
 

提示：

1 <= n <= 104
nums.length == 2 * n
-104 <= nums[i] <= 104

"""

from typing import List


class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        """
        直觉上，应该将相似大小的元素尽量放在一起，会得到最大总和
        实际推理，可以这样考虑：
        假定数组按照从小到大排序（这对最终结果没有影响），
        那么对于最小元素nums[0]，无论使之和哪个元素分配，其min(a1,b1)都必定是nums[0]。
        基于此，nums[0]应该搭配一个除了该元素之外的最小元素nums[1]。如此,其他任意元素进行搭配，都比和nums[1]搭配要更好，因为得到了一个获取更大值的机会。
        以此类推，最佳选择就是使a[i*2]和a[i*2+1]进行搭配，进而获取到最大总和
        而最大总和，就是a[0]+a[2]+...+a[2n-2]


        ps:将排序改为nums.sort(),效率反而会更快
        """

        def merge(left:List[int],right:List[int])->List[int]:
            res=[]
            i,j=0,0
            while i<len(left) and j<len(right):
                if left[i]<right[j]:
                    res.append(left[i])
                    i+=1
                else:
                    res.append(right[j])
                    j+=1
            while i<len(left):
                res.append(left[i])
                i+=1
            while j<len(right):
                res.append(right[j])
                j+=1
            return res
        
        def split_merge(nums:List[int],left:int,right:int)->List[int]:
            if left+1==right:
                return [nums[left]]
            mid=(left+right)//2
            left_res=split_merge(nums,left,mid)
            right_res=split_merge(nums,mid,right)
            return merge(left_res,right_res)
        
        sort_nums=split_merge(nums,0,len(nums))
        sum=0
        for i in range(0,len(nums),2):
            sum+=sort_nums[i]

        return sum

if __name__ == '__main__':
    s = Solution()
    print(s.arrayPairSum([6,2,6,5,1,2]))